# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/5/2 12:28
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : coins_collections.py
@Version     : Version 1.0.0
@Description : TODO 动态规划实现时间复杂度O(n)算法解决拾捡硬币问题
@Created By  : PyCharm
"""


def bottom_top_collect_coins(row_coins):
    """
    自底向上实现递归策略获得累加面值最大拾取硬币子序列的所有子问题的动态规划表
    :param row_coins: 原始硬币列表
    :return: 拾取累加面值最大拾取硬币的子序列索引,最大面值
    """
    i = coins_num = len(row_coins)
    dp_table = [0] * (coins_num + 1)  # 初始化动态规划表
    dp_table[1] = row_coins[0]
    collect_trace = []  # 初始化拾取获得累加面值最大拾取硬币的子序列
    for k in range(2, coins_num + 1):  # 动态规划表比硬币序列长一位
        dp_table[k] = max(dp_table[k - 2] + row_coins[k - 1], dp_table[k - 1])
    # 回溯获得拾取序列索引
    while i >= 1:
        if dp_table[i] > dp_table[i - 1]:  # 确定拾取第i-1个硬币
            collect_trace.append(i - 1)
            i -= 2
        else:
            i -= 1
    collect_trace = collect_trace[::-1]  # 调整倒序累加面值最大拾取硬币的子序列为正序
    return collect_trace, dp_table[-1]


if __name__ == '__main__':
    coins = [5, 1, 2, 10, 6, 2]
    track, max_sub_seq_value = bottom_top_collect_coins(coins)
    print("""原始硬币序列为:{}
拾取累加面值最大硬币的子序列索引为:{}
累加最大面值为:{}""".format(coins,track,max_sub_seq_value ))
